#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

void merge(int *arr, int i, int j, int mid)
{
    // 定义额外的空间暂时存储数据
    vector<int> ret;
    // 开辟空间
    ret.resize(j - i + 1);

    int left = i, right = mid + 1;
    while(left <= mid  && right <= j){
        if(arr[left] < arr[right]){
            ret.push_back(arr[left++]);
        }else{
            ret.push_back(arr[right++]);
        }
    }
    while(left <= mid){
        ret.push_back(arr[left++]);
    }
    while(right <= j){
        ret.push_back(arr[right++]);
    }

    // 将有序的结果写回到arr中
    for(int k{i}, z{0}; k <= j;k++){
        arr[k] = ret[z++];
    }
}

void partition(int *arr, int i, int j)
{
    int *tmp = nullptr;
    // 如果遍历到只剩一个元素，开始回溯
    if(i >= j) return;
    else{
        int mid = (i + j) / 2;
        partition(arr, i, mid);
        partition(arr, mid + 1, j);

        // 回溯的过程
        merge(arr, i, j, mid);
    }
    
}

void sort(int *arr, int len)
{
    int *ret = new int[len]{0};
    partition(arr, 0, len - 1);
    for(int i{}; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(int args, char *argv[])
{
    int arr[] = {7, 3, 9, 1, 0, 4, 3, 8, 11, 13};
    int len = sizeof(arr) / sizeof(int);
    sort(arr, len);
    return 0;
}